Home | | Latest | About | Random
# 02 Solving linear equations, a first look: Echelon form and elementary row operations.
A naive way to solve a system of linear equations in several variables, say $x$, $y$, $z$, is to first solve for one of them using one equation, then substitute into another, then substitute again if necessary, and finally solve. But what if there are a lot of equations and a lot of variables?
We shall find some systematic way to do this. But first we make an observation:
Consider the following linear system: $$
\left\{
\begin{array}{}
3x & + & 4y & - & 2z & = & 0 \\
& & 3y & + & z & = & 2 \\
& & & & 2z & = & 8
\end{array}
\right.
$$
A system that looks like above is much easier to solve -- it is in what we called **echelon form**, a staircase pattern. When it is an echelon form above, we can first solve for the last variable, in this case $2z = 8$, implying $z = 4$. Then **back-substitute** the equation above to get $3y+4=2$ or $y=- 2/3$. Then finally back-substitute once more to get $3x -8 / 3 - 8 = 0$, or $x = 32/ 9$.
So our first strategy is this:
(1) If the linear system is already in echelon form (EF), then great! We can repeatedly back-substitute and solve the system easily.
(2) If the linear system is not already in echelon form, perhaps "manipulate" it somehow so it becomes a system in echelon form, and then solve.
But we have to careful. What do we mean by "manipulate"? We need to do it in a way such that **the solution of the system is preserved**. The manipulated system may look different, but it shall have the **same solution set** in order for this to be useful and correct.
What sort of manipulations can we do to achieve this? These are the **elementary row operations**, which there are three:
(1) **Swap.** Swapping a pair of rows of equations. We denote $$
(R_{i}) \leftrightarrow (R_{j})
$$to mean we swapped row $i$ with row $j$.
(2) **Non-zero scaling.** Scale (multiply) a row of equation by a **non-zero** scalar $k$. We denote this as $$
(R_{i}) \to k (R_{i})
$$to mean we have multiplied row $i$ by some $k \neq 0$. It is important that we scale with a non-zero number, because multiplying by zero to a row effectively removes that row, hence possibly changing the problem!
(3) **Replacement.** We replace a row by adding a multiple of a **different** row to it. We denote this as $$
(R_{i}) \to (R_{i}) + k(R_{j})
$$to mean to the $i$-th row, we add to it a $k$-multiple of row $j$ onto it, where $i \neq j$. It is important that we used a different row, because if we add a $-1$ copy of a row to itself, we get zero!
Each of these elementary row operations will preserve the solution set of a linear system, Also, each of these elementary row operations is **reversible**, that once we applied one of them, we can undo its effect (by applying another appropriate elementary row operation).
Again, note the goal is to apply these operations to produce an echelon form, to which we can back-substitute to solve each variables.
For example, let us solve this following system for unknown $x,y,z$ using this idea: $$
\left\{
\begin{array}{}
3x & + & 2y & - & 2z & =3 \\
2x & + & 4y & + & z & =1 \\
5x & - & y & + & 4z & =2
\end{array}
\right.
$$We can, say, apply $(R_{1})\to \frac{1}{3}(R_{1})$ first, we get $$
\left\{
\begin{array}{}
x & + & \frac{2}{3} y & - & \frac{2}{3}z & =1 \\
2x & + & 4y & + & z & =1 \\
5x & - & y & + & 4z & =2
\end{array}
\right.
$$Then, to clear the $x$'s on row 2, we can apply replacement $(R_{2}) \to (R_{2}) -2(R_{1})$ to get $$
\left\{
\begin{array}{}
x & + & \frac{2}{3} y & - & \frac{2}{3}z & =1 \\
& + & \frac{8}{3} y & + & \frac{7}{3} z & =-1 \\
5x & - & y & + & 4z & =2
\end{array}
\right.
$$Then to clear the $x$'s on row 3, we can apply replacement $(R_{3}) \to (R_{3}) -5(R_{1})$ to get $$
\left\{
\begin{array}{}
x & + & \frac{2}{3} y & - & \frac{2}{3}z & =1 \\
& + & \frac{8}{3} y & + & \frac{7}{3} z & =-1 \\
& - &\frac{13}{3} y & + & \frac{22}{3} z & =-3
\end{array}
\right.
$$
Now perhaps you don't like all the fractions we have so far, so we can perform two non-zero scaling operations here, thought it is not necessary. But let's clear it anyway just for fun.
If we do $(R_{2})\to 3 (R_{2})$ we get $$
\left\{
\begin{array}{}
x & + & \frac{2}{3} y & - & \frac{2}{3}z & =1 \\
& + & 8y & + & 7 z & =-3 \\
& - &\frac{13}{3} y & + & \frac{22}{3} z & =-3
\end{array}
\right.
$$And we continue with $(R_{3})\to 3(R_{3})$ to get $$
\left\{
\begin{array}{}
x & + & \frac{2}{3} y & - & \frac{2}{3}z & =1 \\
& + & 8y & + & 7 z & =-3 \\
& - &13 y & + & 22 z & =-9
\end{array}
\right.
$$We are nearly at an echelon form. We can clear the $y$'s in the last row by another replacement $(R_{3}) \to (R_{3}) + \frac{13}{8} (R_{2})$, and get $$
\left\{
\begin{array}{}
x & + & \frac{2}{3} y & - & \frac{2}{3}z & =1 \\
& + & 8y & + & 7 z & =-3 \\
& & & + & \left( 22 + \frac{13}{8}\cdot7 \right) z & =-9 + \frac{13}{8}(-3)
\end{array}
\right.
$$Now we can solve and back-substitute. Here we have $(22 + 91 /8)z = -9 -39 / 8$, or $\frac{267}{8} z= - 111 / 8$, or $$z = -\frac{111}{267} = - \frac{37}{89}.$$Then back-substitute to get $8y + 7\left( - \frac{37}{89} \right) = -3$, or $8y = - \frac{8}{89}$, or $$
y = - \frac{1}{89}.
$$ And finally we have $x + \frac{2}{3} \left( - \frac{1}{89} \right)- \frac{2}{3} (-\frac{37}{89}) = 1$, or $x = 1+\frac{2}{3(89)} - \frac{74}{3(89)}$, or $$
x= \frac{267+2-74}{267} = \frac{195}{267}= \frac{65}{89}.
$$So the solution to this linear system is $$
x = \frac{65}{89},\ \ \ \ y = - \frac{1}{89},\ \ \ \ z = - \frac{37}{89}.
$$Some remarks. Yes, we can have "nasty" looking answers, like fractions and negatives. But they are just numbers! And there are many different ways to arrive at this answer by using different set of elementary row operations, with different intermediate steps. But if done correctly, they will all give the same answer.